This invention relates to the architecture of multiprocessor data processing systems; and more particularly, it relates to circuits which establish a route from any one data processing node to any other node in such a system.
By a multiprocessor data processing system is herein meant an array of data processing nodes which are interconnected to each other by multiple input/output channels. In this array, each data processing node has an address, and each data processing node can send a message over the input/output channels to any other data processing node. A node which initiates a message is called the source node; and a node which is to ultimately receive the message is called the destination node.
If the source node and the destination node are not connected directly to each other by their input/output channels, then that message must somehow be routed through other nodes in the data processing system which are called intermediate nodes. For example, the message might be routed in a serial fashion from a source node through four or five different intermediate nodes before it reaches the destination node.
In the prior art, multiprocessor data processing systems of the above type, as well as circuits for establishing a route between any two nodes of the system, are described in U.S. Pat. No. 4,814,980 entitled "Concurrent Hypercube System With Improved Message Passing", and U.S. Pat. No. 5,008,882 entitled "Method and Apparatus for Eliminating Unsuccessful Tries In A Search Tree". Also in the prior art are two technical papers by some of the co-inventors of the above patents; and these technical papers are: "Hyperswitch Network For the Hypercube Computer" by E. Chow, H. Madas, J. Peterson, D. Grunwald, and D. Reed, 15th Annual International Symposium On Computer Architecture, May 30-Jun. 2, 1988; and, "A High-Speed Message Driven Communication Architecture" by J. Peterson, E. Chow, and H. Madas, proceedings of the 1988 ACM International Conference on Super-computing, Saint-Malo France, Jul. 4-8, 1988.
In all of the data processing systems which the above patents and papers describe, the total number of data processing nodes is N which is a power of two (N=2.sup.n); and this constraint enables the nodes to be interconnected and operate as a symmetrical array which is called a hypercube. Specifically, in the hypercube, 1) each of the N nodes has "n" input/output channels which are channel(0), channel(1), channel(2), etc.; 2) each and every pair of nodes which are connected together have binary addresses that differ by just one bit b.sub.x ; 3) each connected pair of nodes are connected with a channel(x) to channel(x) connection; and 4) a channel is selected to route a message to a destination node only if that channel decreases the distance to the destination by exactly one node.
However, a serious practical drawback with the hypercube system in that the number of nodes which the hypercube must have is too limited. For example, suppose a customer with a 128 node hypercube system (N=2.sup.7) wants to expand his system. To do that, the number of nodes must be increased to 2.sup.8 or 256; so another 128 nodes must be added to the existing system! This large increase in the total number of nodes will double the cost of network and be completely impractical for a customer who only wants to add just a few more nodes to his existing system. But, in the above cited patents and papers, the array must have 2.sup.n nodes; and, with the message routing circuits which are disclosed, a multiprocessor system having other than 2.sup.n nodes will not work.